package com.vint.leetcode;

import com.vint.common.TreeNode;

/*
 * 合并两个二叉树
 */
public class Leetcode617 {
    /*
     * 原树节点不能打乱
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (null == t1){
            return t2;
        }
        if (null == t2){
            return t1;
        }
        //这里浪费了空间，应该复用这两个节点，前提是这两个节点的Tree可以被打乱
        TreeNode root = new TreeNode(t1.val + t2.val);
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }

    /*
     * 节约空间，复用之前Node, 前提是可以打乱
     */
    public TreeNode mergeTrees1(TreeNode t1, TreeNode t2) {
        if (null == t1){
            return t2;
        }
        if (null == t2){
            return t1;
        }
        t1.val += t2.val;
        t1.left = mergeTrees1(t1.left, t2.left);
        t2.right = mergeTrees1(t1.right, t2.right);
        return t1;
    }

    public void visitDouble(TreeNode t1, TreeNode t2){
            if(t1 != null  && t2 != null){
                t1.val += t2.val;
            }

            // t1 left t2 no left
            if(t1.left != null && t2.left ==null){
                t2.left = new TreeNode(0);    //error: t2.left is null means t2 hasnot left, why you add left subtree into t2. just as follows case.
                visitDouble(t1.left, t2.left);     //complier Error: visit?
            }

            // t1 no left t2 left
            if(t1.left == null && t2.left != null){
                t1.left = new TreeNode(0);
                visitDouble(t1.left, t2.left);
            }

            //t1 right  t2 no right
            if(t1.right != null && t2. right == null){
                t2.right = new TreeNode(0);
                visitDouble(t1.right, t2.right);
            }

            // t1 no right  t2 right
            if(t1.right == null && t2.right != null){
                t1.right = new TreeNode(0);
                visitDouble(t1.right, t2.right);
            }

            if(t1.left != null && t2.left != null){
                visitDouble(t1.left, t2.left);
            }

            if(t1.right != null && t2.right != null){
                visitDouble(t1.right, t2.right);
            }

            return;

            //Exception:
            //1. t1 is null, t2 is null?
            //2. t1 is null, t2 is not null? or t1 is not null, t2 is null
            //3 t1 and t2 are orginal tree the system set, can we change their structures? if can, how to do? if can't, how to do
            //4. t1 has left & t2 has left or t1 has right&t2 has right

        }

    public static void main(String[] args) {
        TreeNode root1 = TreeNode.mockTree();
        TreeNode root2 = TreeNode.mockTree();
        TreeNode root3 = TreeNode.mockSpecific1();
        TreeNode root4 = TreeNode.mockSpecific2();
        Leetcode617 sixOneSeven = new Leetcode617();
        //TreeNode root = sixOneSeven.mergeTrees(root1, root2);
        //TreeNode root = sixOneSeven.mergeTrees(root3, root4);
        sixOneSeven.visitDouble(root3, root4);
        System.out.println("success!");
    }
}
